/**
 * 给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

 

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4
示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthLargest = function (root, k) {
    //中序遍历
    const res = []
    let inorder = (root) => {

        if (!root) return

        inorder(root.right)
        res.push(root.val)
        inorder(root.left)
    }
    inorder(root)
    console.log(res)
    return res[k - 1]
};


/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
var kthLargest1 = function (root, k) {
    if (!root) return 0;
    // 声明储存栈
    const stack = [];
    // 判断当前栈否有节点和当前遍历节点位置
    while (stack.length || root) {
        while (root) {
            // 往栈里添加当前节点，同时切换为右节点处理
            stack.push(root);
            root = root.right;
        }
        // 取出当前栈顶元素，根据添加的顺序，当前元素是栈内最大的
        const cur = stack.pop();
        k--;
        if (k === 0) return cur.val;
        // 切换为左节点处理
        root = cur.left;
    }
    return 0;
};